/* 
 * File:   heap.h
 * Author: aishwarya
 *
 * Created on March 12, 2011, 3:42 AM
 * Binary Heap - Interface definition
 */
#include "avdtech.h"

#ifndef HEAP_H
#define	HEAP_H

#ifdef	__cplusplus
extern "C" {
#endif

#define PARENT(i)	((i)/2)		/* Parent of node i */
#define LEFT(i)		(2*(i))		/* Left child of node i */
#define RIGHT(i)	((2*(i))+1)	/* Right child of node i */

    typedef struct _binary_heap {
        /* Functions to compare, print, copy, delete the elements of this heap */
        KEYCMP _keycmpfn;
        DATACPY _datacpyfn;
        DELNODE _delnodefn;
        PRINTNODE _printfn;

        char *elements; /* Dynamic array representing the binary heap */
        /* elements[] is an array of generic structures of size 'e_size' */
        size_t e_size; /* Size of one element */
        UINT nelements; /* Pre-allocated length of array elements[] */
        UINT heap_size; /* Size of the binary heap */
        int *indexOf; /* Get the index in heap of the application object with identifier <id> */
        int *handleAt; /* Instead of moving data in elements[], move pointers to elements[] <i> */
    } BINARY_HEAP;

    /* Index in heap starts from 1. So application should pass ID from [1...nelements].
     * Heap functions return 0 on failure (index out of heap bounds)
     */
    void heap_init(BINARY_HEAP *h, UINT initial_size, size_t e_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p);
    void heap_clean(BINARY_HEAP *h);
    UINT min_heap_insert(BINARY_HEAP *h, UINT id, const void * n);
    UINT max_heap_insert(BINARY_HEAP *h, UINT id, const void * n);
    UINT heap_increase_key(BINARY_HEAP *h, UINT id, const void * n);
    UINT heap_decrease_key(BINARY_HEAP *h, UINT id, const void * n);
    UINT heap_extract_max(BINARY_HEAP *h, void *min);
    UINT heap_extract_min(BINARY_HEAP *h, void *min);
    UINT heap_maximum(BINARY_HEAP *h, void *min);
    UINT heap_minimum(BINARY_HEAP *h, void *min);
    void max_heapify(BINARY_HEAP *h, UINT i);
    void min_heapify(BINARY_HEAP *h, UINT i);

#ifdef	__cplusplus
}
#endif

#endif	/* HEAP_H */

